package service.week01.leetcode.editor.cn;
//给你一个整数数组 nums 和一个整数 k。 
//
// 如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。 
//
// 请返回这个数组中「优美子数组」的数目。 
//
// 
//
// 示例 1： 
//
// 输入：nums = [1,1,2,1,1], k = 3
//输出：2
//解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
// 
//
// 示例 2： 
//
// 输入：nums = [2,4,6], k = 1
//输出：0
//解释：数列中不包含任何奇数，所以不存在优美子数组。
// 
//
// 示例 3： 
//
// 输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
//输出：16
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 50000 
// 1 <= nums[i] <= 10^5 
// 1 <= k <= nums.length 
// 
// Related Topics 双指针 
// 👍 172 👎 0

public class P1248CountNumberOfNiceSubarrays {
    public static void main(String[] args) {
        Solution solution = new P1248CountNumberOfNiceSubarrays().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 前缀和
         *
         * @param nums
         * @param k
         * @return
         */
        public int numberOfSubarrays(int[] nums, int k) {
            int len = nums.length;
            int[] s = new int[len + 1];
            //计算次数
            int[] count = new int[len + 1];
            //1，转为0/1 并且求前缀和
            for (int i = 1; i <= len; i++) {
                //这里为什么是nums[n-1],可以假设第一位是0
                s[i] = s[i - 1] + nums[i - 1] % 2;
            }
            //计数
            for (int i = 0; i < len; i++) {
                count[s[i]] += 1;
            }
            //s[j]-k>=0
            int res = 0;
            //前缀和从1开始
            for (int i = 1; i <= len; i++) {
                if (s[i] - k > 0) {
                    res += count[s[i] - k];
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}